//循环队列

#pragma

//循环队列类型定义
template <typename E, int MAXSIZE = 256>
struct SqQueue
{
    E elem[MAXSIZE];
    int front, rear;
};

//初始化循环队列为空 InitQueue(&Q)
template <typename E, int MAXSIZE>
void InitQueue(SqQueue<E, MAXSIZE> &Q)
{
    Q.front = Q.rear = 0;
}

//判断循环队列是否为空 QueueEmpty(Q)
template <typename E, int MAXSIZE>
bool QueueEmpty(const SqQueue<E, MAXSIZE> &Q)
{
    return Q.front == Q.rear;
}

//入队列EnQueue(&Q, e)
template <typename E, int MAXSIZE>
void EnQueue(SqQueue<E, MAXSIZE> &Q, E e)
{
    //若队列满，则抛出异常
    if((Q.rear + 1) % MAXSIZE == Q.front)
        throw "queue full";
    //否则，将 e 插入队尾
    Q.elem[Q.rear] = e;
    Q.rear = (Q.rear  + 1) %MAXSIZE;
}

//出队列 DeQueue(&Q, &e)
template <typename E, int MAXSIZE>
void DeQueue(SqQueue<E, MAXSIZE> &Q, E &e)
{
    //若队列空，则抛出异常
    if(Q.front == Q.rear)
        throw "queue empty";
    //否则，删除队头元素，用 e 返回
    e = Q.elem[Q.front];
    Q.front = (Q.front  + 1) % MAXSIZE;
}

//取队头元素 GetHead(Q, &e)
template <typename E, int MAXSIZE>
void GetHead(const SqQueue<E, MAXSIZE> &Q, E &e)
{
    //若队列空，则抛出异常
    if(Q.front == Q.rear)
        throw "queue empty";
    //否则，用 e 返回队头元素
    e = Q.elem[Q.front];
}

//求队列长度 QueueLength(Q)
template <typename E, int MAXSIZE>
int QueueLength(const SqQueue<E, MAXSIZE> &Q)
{
    //if(Q.rear >= Q.front)
    //    return Q.rear - Q.front;
    //else
    //    return Q.rear + MAXSIZE - Q.front;
    return (Q.rear + MAXSIZE - Q.front) % MAXSIZE;
}